#pragma once

#include <list>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

// Grafo implementado na forma de uma estrutura de adjacência
template<typename V = char, typename E = char>
class AdjacenceStructGraph
{
  struct Edge
  {
    E value;
    int node; 

    // no contexto atual, só precido comparar o nó, não o valor
    bool operator==(const Edge &other) const
    {
      return node == other.node;
    }
  };

  typedef list<Edge> Adjacences;

  struct Node
  {
    V value;
    Adjacences adjacences;
  };

  vector<Node> _nodes;

  void insertEdjeOnNode(int origNode, int dstNode, const E &value)
  {
    Node &n = _nodes[origNode];
    n.adjacences.push_back({value,dstNode});
  }

  int getNodeDegree(const Node &node) const
  {
    return node.adjacences.size();
  }

public:
  int addNode(const V &value = V())
  {
    _nodes.push_back({value,{}});
    return _nodes.size() - 1;
  }

  const V &getNodeValue(int n) const
  {
    return _nodes[n].value;
  }

  int countNodes() const
  {
    return _nodes.size();
  }

  int getNodeDegree(int node) const
  {
    return _nodes[node].adjacences.size();
  }

  int countEdges() const
  {
    int count = 0;

    for (const Node &node: _nodes) {
      count += getNodeDegree(node);
    }

    return count/2;
  }

  bool isAValidNode(int node) const
  {
    int lastIndex = _nodes.size() - 1;
    return node <= lastIndex;
  }
  
  bool addEdge(int node1, int node2, const E &value = E())
  {
    int lastIndex = _nodes.size() - 1;

    // não posso ter loops nem tentar adicionar arestas entre nós que não existem
    if (!isAValidNode(node1) || !isAValidNode(node2) || node1 == node2) {
      return false;
    }

    insertEdjeOnNode(node1, node2, value);

    insertEdjeOnNode(node2, node1, value);

    return true;
  }
  
  bool areNodesAdjacents(int node1, int node2)
  {
    // FIXME: cópia do código de addEdge!
    // não posso ter loops nem tentar adicionar arestas entre nós que não existem
    if (!isAValidNode(node1) || !isAValidNode(node2) || node1 == node2) {
      return false;
    }
  
    const Adjacences &adjacences(_nodes[node1].adjacences);

    Edge edge {E(),node2};
    
    // node2 está na adjacencesa de adjacência de node1?
    return find(adjacences.begin(),adjacences.end(),edge) != adjacences.end();
  }
  
  const E &getEdgeValue(int node1, int node2) const
  {
    Edge edge {E(),node2};
    const Adjacences &adjacences(_nodes[node1].adjacences);
    return find(adjacences.begin(),adjacences.end(),edge)->value;
  }

  vector<int> getAdjacentNodes(int node) const
  {
    vector<int> r;
    for (auto edge: _nodes[node].adjacences) {
      r.push_back(edge.node);
    }
    return r;
  }
};
